package com.wtgroup.demo.面试题.我的面试.华为OD笔试230627;

import java.util.ArrayList;
import java.util.Scanner;

/**
 * 非叶子节点后序遍历
 */

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Q1_非叶子节点后序遍历 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        ArrayList<Integer> list = new ArrayList<Integer>();
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            list.add(a);
        }

        Integer[] treeArr = list.toArray(new Integer[0]);
        ArrayList<Integer> result = new ArrayList<Integer>();
        func(treeArr, 0, result);

        for (int j = 0; j < result.size(); j++) {
            if (j > 0) {
                System.out.print(" ");
            }
            Integer i = result.get(j);
            System.out.print(i);
        }
    }

    static void func(Integer[] treeArr, int i, ArrayList<Integer> result) {
        if (i >= treeArr.length) {
            return;
        }

        int leftIx = 2 * i + 1;
        if (leftIx >= treeArr.length && i > 0) {
            // 叶子节点
            return;
        }

        // if (leftIx < treeArr.length) {
        func(treeArr, leftIx, result);
        // }
        if (leftIx + 1 < treeArr.length) {
            func(treeArr, leftIx + 1, result);
        }
        result.add(treeArr[i]);
    }
}
